1. Field of the Invention
The present invention relates to signal processing, and, in particular, to the routing of communication signals through a sliced switch fabric.
2. Description of the Related Art
In a typical multi-user communication system, such as a telephony system, signals are transmitted back and forth between different users. Such a system typically has one or more switch nodes, each of which is responsible for receiving a plurality of incoming signals from one or more different sources and routing those signals for transmission as outgoing signals to one or more different destinations. It is desirable to verify that a switch node is correctly configured to route incoming signals to the appropriate destinations.
One conventional technique for verifying the configuration of a switch node is to encode each incoming signal with a special binary code word that identifies that incoming signal. This special binary code word is often referred to as a trace word, because it can be used to trace the path of a signal through the different components of the communication system. By decoding the trace word contained in each outgoing signal transmitted from the switch node, it can be determined if the switch node is properly configured.
In order to attempt to ensure that the configuration of a switch node can always be verified, in conventional techniques, each incoming signal is assigned a unique trace word. In order for each incoming signal to have a unique trace word, the binary trace word must have at least as many bits as needed to assign a different trace word to each incoming signal for up to the maximum number of concurrent signals that the switch node can handle. For example, if a particular switch node can support up to 218 different incoming signals at one time, the binary trace word encoded into each incoming signal must have at least 18 bits in order to ensure that each incoming signal can be assigned a different trace word. Since trace words take up space in the signal bit stream, it is generally desirable to keep trace words as short as possible, especially in systems having limited bandwidth for such overhead information. A shorter trace word also allows a misconnection to be detected more quickly.
In order to handle faster and faster data rates, some conventional switch nodes are designed with a sliced switch fabric architecture, in which multiple switches operate in parallel on different subsets of data from each incoming signal. In a bit-sliced architecture, each incoming serial data stream is parallelized on a bit-by-bit basis. That is, each data stream is demultiplexed in one-bit segments into two or more parallel streams, where each parallel stream comprises a subset of the bits of the original data stream. Other types of sliced architectures are also possible, such as byte-sliced architectures, in which serial data streams are parallelized on a byte-by-byte basis.
FIG. 1 shows a block diagram of the bit-sliced switch fabric 100 of a typical switch node having a sliced architecture. Switch fabric 100 has a column of n input demultiplexers 102, a column of m switches 104, and a column of n output multiplexers 106, where n is the maximum number of incoming signals supported by switch fabric 100 and m is the number of switches operating in parallel within switch fabric 100. A controller 108 assigns a different trace word to each different processor 110 and each processor 110 encodes its assigned trace word into the corresponding incoming signal.
Each demultiplexer 102 can receive and parallelize a different incoming signal on a bit-by-bit basis, whereby every mth bit of the incoming signal is transmitted to the same parallel switch 104. For example, in a particular embodiment of switch fabric 100 in which there are m=8 switches 104 operating in parallel, and assuming that switch fabric 100 is fully loaded with n incoming signals, each demultiplexer 102 transmits (1) the first bit of every 8-bit byte in the corresponding incoming signal to the first switch 104a in the column of parallel switches, (2) the second bit of every 8-bit byte in the corresponding incoming signal to the second switch 104b, and so on, for each bit and each switch 104.
Each switch 104 switches the corresponding subset of each incoming signal to a different output multiplexer 106. For example, the first switch 104a switches the first bit of each 8-bit byte for each incoming signal to a different output multiplexer 106. When properly configured, all of the switches 104 are configured identically to switch the corresponding subsets of the incoming signals to the appropriate output multiplexers 106.
Each output multiplexer 106 can receive and serialize bits for a different outgoing signal. In the example in which switch fabric 100 has eight switches 104, each multiplexer 106 receives from each of the eight switches 104 a different bit for each byte of an outgoing signal and serializes those bits to form the outgoing signal. That is, each multiplexer 106 receives the first bit of each 8-bit byte of the corresponding outgoing signal from the first switch 104a, the second bit of each 8-bit byte of the same outgoing signal from the second switch 104b, and so on, for each bit and every switch 104. Each output multiplexer 106 serializes the eight parallel streams of bits received from the eight switches 104 to form a single serial stream corresponding to the output signal.
As with other switch nodes, it is desirable to be able to verify that a switch node having a sliced architecture is configured properly. There are two basic types of improper configuration for a switch node having a sliced switch fabric such as switch fabric 100 of FIG. 1.
The first type of improper switch configuration is when all of the parallel switches 104 except one are properly configured. In this case, at least one bit of each byte of at least one incoming signal is either not routed at all or is routed by the improperly configured switch to the wrong output multiplexer 106. A particular example of this type of improper switch configuration occurs when one of the switches 104 simply fails to operate at all, in which case none of the bits received by that switch will be routed to any output multiplexer 106 and each corresponding bit in each outgoing signal will be the same (e.g., zero).
The second type of improper switch configuration is when all of the parallel switches 104 are configured identically, but incorrectly. In this case, all of the bits of at least one incoming signal is routed to the wrong output multiplexer 106.
Of course, the situation could exist where two or more, but less than all of the parallel switches 104 were misconfigured (either identically or differently) at the same time. This would be considered to be an example of two or more concurrent instances of the first type of improper switch configuration.
Unfortunately, the conventional technique of assigning a trace word to each incoming signal does not guarantee accurate determination of whether or not each and every parallel switch in a sliced architecture is configured properly. Using the conventional technique, one or more of the parallel switches could be improperly configured without being able to be detected by analyzing the conventional trace words contained in the outgoing signals.
Take, for example, a particular bit-sliced switch fabric having 216 input demultiplexers and 216 output multiplexers supporting up to 216 different incoming signals and 8 parallel switches. Assume that a first incoming signal is assigned the following conventional 16-bit trace word:
(1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0),
while a second incoming signal is assigned the following different conventional 16-bit trace word:
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1).
Assume further that the first incoming signal is supposed to be routed from the first input demultiplexer to the first output multiplexer, while the second incoming signal is supposed to be routed from the second input demultiplexer to the second output multiplexer. Because of the particular nature of these two trace words, every trace-word bit received by the first switch for both of these two incoming signals will have the value xe2x80x9c1xe2x80x9d. As such, if all of the switches except the first switch were properly configured, and the first switch were improperly configured to switch the first incoming signal from the first input demultiplexer to the second (instead of the first) output multiplexer and the second incoming signal from the second input demultiplexer to the first (instead of the second) output multiplexer, such an improper configuration could not be detected by analyzing the trace words contained in the two outgoing signals generated by the first and second output multiplexers. This is because each of the trace words in the two outgoing signals would always be correct, even though the first switch would be improperly routing bits, since all of those improperly routed bits would have the same value of xe2x80x9c1xe2x80x9d.
Thus, the conventional technique of assigning trace words fails to ensure that the configuration of each and every parallel switch in a sliced switch fabric can always be verified.
The present invention is directed to a scheme for verifying the configuration of each and every parallel switch in a switch fabric having a sliced architecture. According to the present invention, a trace word is assigned to each and every incoming signal such that, not only does the trace word uniquely identify the incoming signal, but each sliced trace wordxe2x80x94that is, the subset of trace word bits processed by each of the parallel switchesxe2x80x94also uniquely identifies the incoming signal. This scheme ensures that the configuration of each and every parallel switch can always be verified for all incoming signals.
In one embodiment, the present invention is a method and apparatus for verifying the switch configuration of a sliced switch fabric having a plurality of parallel switches. Each incoming signal is assigned a unique trace word, and the unique trace word is encoded into each incoming signal in accordance with an overall format that ensures that each sliced trace word routed by each parallel switch uniquely identifies the corresponding incoming signal, thereby ensuring that the switch configuration of each and every parallel switch can be verified.